1. Field of the Invention
This invention relates to an apparatus for effectively transferring overflow/underflow data from a stack buffer to an external overflow stack.
2. Description of Prior or Contemporary Art
Computer designers have for years attempted to use a rapidly accessible buffer or stack cache that is associated with a slower or more remote main memory. An article entitled "The Mechanization of a Push-down Stack", written by C. B. Carlson (AFIPS Conf. Proc., V. 24, 1963), describes an early Burroughs machine that places the top two elements of a stack in machine registers with the rest in main memory. Similarly, an early article by Russell P. Blake entitled "Exploring a Stack Architecture" (IEEE Computer, 10, 5, May 1977) describes the buffer stack arrangement in the early HP 3000 computer system.
More recently attempts have been made to optimize cache management for the C-language, a general purpose computing language. An article entitled "Register Allocation for Free: The C Machine Stack Cache", written by D. R. Ditzel and H. R. McLellan (Proc. Symposium on Architectural Support for Programming Languages and Operating Systems, March, 1982) describes a cache management scheme that allocates a stack frame in the cache memory. The size of the frame is determined by the number of registers necessary to perform a particular procedure. The number/register written out of or into the cache is determined by the space needed for the procedure frame. An article entitled "Strategies for Managing the Register file in RISC" written by Y. Tamir and C. H. Sequin (IEEE Transection on Computers, Vol. C-32, No. 11, November 1983) describes a RISC (reduced instruction set computer) architecture utilizing a cache arrangement in which a register window is set up for each procedure. The output from one procedure becomes the input of a called procedure through overlapping register window. When overflow or underflow occurs, an entire register window (comprised of 16 registers) is written out of or into the stack cache. An article entitled "Sun Builds an Open RISC Architecture" by Robert B. Garner (Sun Technology, Summer 1988) describes the implementation of the same RISC cache management scheme in a commercial processor chip. Again, the single processor chip embodiment transfers fixed windows comprising multiple register values with each overflow or underflow.
An article entitled "High Speed Top-of-Stack Scheme for VLSI Processor" by M. Hasegawa and Y. Shigei (Proc. of the 12th Annual International Symposium on Computer Architecture, pp. 48-54, 1985) is a theoretical study of a cache stack to determine the optimum management scheme. The article assumes that stack depth is a random walk function. Applicants have shown this assumption to be false and have found that the cache depth reaches a particular value and then proceeds to oscillate slightly around that value. As a result, the optimum cache stack management scheme suggested by the above article differs from the scheme described in this patent application.